package Hot100;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-12-26 14:37
 */
public class isValidBST98 {

    /**98. 验证二叉搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：节点的左子树只包含 小于 当前节点的数，节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
     * 递归，先判断左右子树分别为有效BST，然后判断当前根是否满足,不能只判断根节点与左右节点的值，
     * */
    //min和max分别记录左右子树中的最大节点和最小节点
    boolean isValid(TreeNode root,TreeNode min,TreeNode max){
        if (root==null) return true;
        if (min!=null&&root.val<=min.val) return false;
        if (max!=null&&root.val>=max.val) return false;
        //限定左子树的最大值是root，右子树的最小值是root
        return isValid(root.left,min,root)&&isValid(root.right,root,max);
    }
    public boolean isValidBST(TreeNode root) {
        return isValid(root,null,null);
    }

    /**700. 二叉搜索树中的搜索
     * 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
     * 递归查找
     * */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root==null) return null;
        if (root.val==val) {
            return root;
        }else if (root.val>val){
            return searchBST(root.left,val);
        }else {
            return searchBST(root.right,val);
        }
    }

    /**
     * 在BST中插入一个数
     * */
    TreeNode insertIntoBST(TreeNode root, int val) {
        if (root==null) return new TreeNode(val);
        if (root.val>val){
            //在左子树中插入
            root.left = insertIntoBST(root.left, val);
        }
        if (root.val<val){
            root.right=insertIntoBST(root.right,val);
        }
        return root;
    }

    /**
     * 在BST中删除一个数，若A为要删除的节点，有以下情况
     * 1、A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了。
     * 2、A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。
     * 3、A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己
     * */
    TreeNode getMin(TreeNode root){
        while (root.left!=null) root=root.left;
        return root;
    }
    TreeNode deleteNode(TreeNode root, int key) {
        if (root==null) return null;
        if (root.val==key){
            //删除当前节点：
            //情况1，2
            if (root.left==null) return root.right;
            if (root.right==null) return root.left;
            //情况3：用右子树的最小节点代替当前节点
            TreeNode min=getMin(root.right);
            //先删除右子树中的最小节点
            root.right=deleteNode(root.right,min.val);
            //用min代替root节点
            min.left=root.left;
            min.right=root.right;
            root=min;
        }else if (root.val<key){
            root.left=deleteNode(root.left,key);
        }else {
            root.right=deleteNode(root.right,key);
        }
        return root;
    }
}
